﻿Imports System.Math

Partial Public Class ExpressionNode
    ' Parse the expression to build the expression tree.
    Private Sub ParseExpression()
        ' If the expression is blank, the value is 0.
        If Expression.Length = 0 Then
            Expression = "0"
            Exit Sub
        End If

        ' If the first thing is + or -, it's unary.
        Dim is_unary As Boolean = True

        ' So far we've found no operator.
        Dim best_prec As Precedence = Precedence.None

        ' Find the operator with the lowest precedence.
        ' Look for places where there are no open parentheses.
        Dim open_parens As Integer = 0
        Dim best_i As Integer = -1
        For i As Integer = 0 To Expression.Length - 1
            ' Assume we will not find an operator. In that case,
            ' the next operator will not be unary.
            Dim next_unary As Boolean = False

            ' Examine the next character.
            Dim ch As String = Expression.Substring(i, 1)

            ' Examine the next character.
            If ch = " " Then
                ' Skip spaces. We keep them to make
                ' error messages easier to read.
            ElseIf ch = "(" Then
                ' Increment the paren count.
                open_parens += 1

                ' A + or - after "(" is unary.
                next_unary = True
            ElseIf ch = ")" Then
                ' Decrement the paren count.
                open_parens -= 1

                ' An operator after ")" is not unary.
                next_unary = False

                ' If paren count < 0, too many ')'s.
                If open_parens < 0 Then
                    Throw New Exception("Parse error. Too many )s in expression '" & Expression & "'")
                End If
            ElseIf open_parens = 0 Then
                ' We have no open parentheses.
                ' See if it's an operator.
                If ch = "^" OrElse ch = "*" OrElse _
                   ch = "/" OrElse ch = "\" OrElse _
                   ch = "%" OrElse ch = "+" OrElse _
                   ch = "-" _
                Then
                    ' An operator after an operator is unary.
                    next_unary = True

                    ' See if this operator has higher
                    ' precedence than the current one.
                    Select Case ch
                        Case "^"
                            If best_prec >= Precedence.Power Then
                                best_prec = Precedence.Power
                                best_i = i
                            End If

                        Case "*", "/"
                            If best_prec >= Precedence.Times Then
                                best_prec = Precedence.Times
                                best_i = i
                            End If

                        Case "\"
                            If best_prec >= Precedence.IntDiv Then
                                best_prec = Precedence.IntDiv
                                best_i = i
                            End If

                        Case "%"
                            If best_prec >= Precedence.Modulus Then
                                best_prec = Precedence.Modulus
                                best_i = i
                            End If

                        Case "+", "-"
                            ' Ignore unary operators
                            ' for now.
                            If (Not is_unary) AndAlso _
                                best_prec >= Precedence.Plus _
                            Then
                                best_prec = Precedence.Plus
                                best_i = i
                            End If
                    End Select
                End If
            End If
            is_unary = next_unary
        Next i

        ' Make sure the open paren count is zero.
        If open_parens <> 0 Then
            Throw New Exception("Parse error. Missing ) in expression '" & Expression & "'")
        End If

        ' See if we have an operator.
        If best_prec < Precedence.None Then
            Dim lexpr As String = Expression.Substring(0, best_i)
            Dim rexpr As String = Expression.Substring(best_i + 1)
            Op = Expression.Substring(best_i, 1)

            LeftChild = New ExpressionNode(lexpr)
            RightChild = New ExpressionNode(rexpr)
            Exit Sub
        End If

        ' We don't have an operator yet. 
        ' There are several possibilities:
        '
        ' 1. Expression is (expr2) for some expr2.
        ' 2. Expression is -expr2 or +expr2 for some expr2.
        ' 3. Expression is Fun(expr2) for some function Fun.
        ' 4. Expression is a literal like "3.14159".

        ' Look for (expr2).
        If Expression.StartsWith("(") AndAlso Expression.EndsWith(")") Then
            ' Remove the parentheses.
            Op = "( )"
            LeftChild = New ExpressionNode(Expression.Substring(1, Expression.Length - 2))
            Exit Sub
        End If

        ' Look for -expr2.
        If Expression.StartsWith("-") Then
            Op = "-"
            LeftChild = New ExpressionNode(Expression.Substring(1, Expression.Length - 1))
            Exit Sub
        End If

        ' Look for +expr2.
        If Expression.StartsWith("+") Then
            Op = "+"
            LeftChild = New ExpressionNode(Expression.Substring(1, Expression.Length - 1))
            Exit Sub
        End If

        ' Look for Fun(expr2).
        If Expression.Length > 5 AndAlso Expression.EndsWith(")") Then
            ' Find the first (.
            Dim pos As Integer = Expression.IndexOf("(")

            If pos > 0 Then
                ' See what the function is.
                Op = Expression.Substring(0, pos)

                Dim expr As String = Expression.Substring(pos + 1, Expression.Length - pos - 2)
                LeftChild = New ExpressionNode(expr)

                Exit Sub
            End If
        End If

        ' It must be a literal such as "2.71828".
        Exit Sub
    End Sub

    ' Evaluate the parsed tree.
    Public Function Evaluate() As Double
        ' See if we have an operand.
        If Op = "" Then
            ' No operand. This is a literal.
            Return Double.Parse(Expression)
        Else
            ' See what the operand is.
            Select Case Op.ToLower()
                Case "^"        ' Power.
                    Return LeftChild.Evaluate() ^ RightChild.Evaluate()
                Case "*"        ' Times.
                    Return LeftChild.Evaluate() * RightChild.Evaluate()
                Case "/"        ' Divide.
                    Return LeftChild.Evaluate() / RightChild.Evaluate()
                Case "\"        ' Integer divide.
                    Return LeftChild.Evaluate() \ RightChild.Evaluate()
                Case "%"        ' Modulus.
                    Return LeftChild.Evaluate() Mod RightChild.Evaluate()
                Case "+"        ' Plus or unary plus.
                    If RightChild Is Nothing Then
                        ' Unary +.
                        Return +LeftChild.Evaluate()
                    Else
                        ' Binary +.
                        Return LeftChild.Evaluate() + RightChild.Evaluate()
                    End If
                Case "-"        ' Minus or unary minus.
                    If RightChild Is Nothing Then
                        ' Unary -.
                        Return -LeftChild.Evaluate()
                    Else
                        ' Binary -.
                        Return LeftChild.Evaluate() - RightChild.Evaluate()
                    End If
                Case "( )"      ' Parentheses.
                    Return LeftChild.Evaluate()
                Case "sin"      ' Sine.
                    Return Sin(LeftChild.Evaluate())
                Case "cos"      ' Cosine.
                    Return Cos(LeftChild.Evaluate())
                Case "tan"      ' Tangent.
                    Return Tan(LeftChild.Evaluate())
                Case "sqr"      ' Square root.
                    Return Sqrt(LeftChild.Evaluate())
                Case "factorial" ' Factorial.
                    Return Factorial(LeftChild.Evaluate())
                Case Else
                    Throw New Exception("Evaluate error. Unknown function '" & Op & "'")
            End Select
        End If
    End Function

    Private Function Factorial(ByVal N As Double) As Double
        ' Make sure it's an integer.
        If CType(N, Long) <> N Then
            Throw New Exception("Factorial error. Argument " & N.ToString() & " must be an integer")
        End If

        Dim result As Double = 1
        Do While N > 1
            result *= N
            N -= 1
        Loop
        Return result
    End Function
End Class

